A digital image is typically displayed or printed in the form of a rectangular array of "picture elements" or "print elements". For purposes of this application, both "picture elements" and "print elements" are referred to herein as "pixels". Digital images are typically represented in a computer by one or more arrays of binary numbers. For example, a monochrome digital image can be represented in a computer by a single array of binary numbers. Each binary number in the array defines a gray-level value for an associated pixel. The position of the binary number in the array describes the spatial location of the pixel.
A color digital image can be represented in a computer by three arrays of binary numbers. Each array (alternatively referred to herein as an "image plane") representing an axis of a suitable color coordinate system in accordance with the well known trichromatic theory. The color of a pixel in the digital image is defined by an associated binary number (defining one of three color components from the color coordinate system) from each array. It is noted that there are many color coordinate systems that can be used to represent the color of a pixel. These color coordinate systems include a "Red-Green-Blue" (RGB) coordinate system, a cyan-magenta-yellow (CMY) coordinate system and a luminescence (Y), red-yellow (Cr) and blue-yellow (Cb) color coordinate system. The former is commonly used in monitor display applications, the latter is commonly used in printing applications.
The amount of data used to represent a digital image can be extremely large. Consider, for example, a color digital image consisting of 1024.times.1024 pixels. If the pixels are represented in the computer by three image planes of 8-bit numbers, the digital image would occupy over 1 megabyte of storage space.
The large amount of data required to represent a digital image in a computer can result in significant costs that are associated both with increased storage capacity requirements, and the computing resources and time required to transmit the data to another computing device. In order to reduce these costs, digital image compression techniques have been and are continuing to be developed.
Digital image compression techniques can generally be divided into two classes: lossless and lossy. In lossless compression, the digital image reconstructed after compression is identical, pixel by pixel, to the original image. In lossy compression, the reconstructed digital image is degraded with respect to the original digital image in order to attain higher compression ratios than those of lossless procedures. One popular lossy compression scheme is referred to as "transform coding". See Baxes, G. A., Digital image Processing, Principles and Applications, pp 198-211, ISBN 0-471-00949-0 (1994). Those pages are incorporated herein by reference. A widely used transform coding scheme has been standardized by the published and generally available works of the Joint Photographic Experts Group (JPEG).
An encoding system that includes a transform encoder to encode a digital image will typically also have an entropy encoder to further compress the data generated by the transform encoder. See Pennebaker, W. B., and Mitchell, J. L., JPEG: Still Image Compression Standard, pp 65-79 and pp189-201, ISBN 0-442-01272-1 (1993). Those pages are incorporated herein by reference.
One popular entropy coding technique is referred to as Huffman coding. A Huffman encoder will typically utilize a Huffman statistical model to convert the output of a transform encoder into a series of symbols that represents an intermediate representation of the digital image. The Huffman encoder then operates to assign short code words to the symbols that occur most often and longer code words to the less probable symbols. The code words that are used in Huffman encoding are typically obtained from one or more tables, known as Huffman Tables. The resulting data represents the digital image in compressed form and is referred to herein as "Huffman encoded data".
Although Huffman coding is generally considered the best fixed length coding procedure available, the fact that the Huffman codes are an integral number of bits long can result in non-optimal coding. This can become a problem in the case when the probability of a particular character is high. See Nelson, M. and Gaily J., The Data Compression Book, pp113-114, ISBN 1-55851-434-1 (1995). Those pages are incorporated herein by reference.